1. Field of the Invention
The present invention relates to the field of circuit design and, more particularly, to deriving a legal placement for a circuit design.
2. Description of the Related Art
One important task in the process of implementing a circuit design from a hardware description language (HDL), such as VHDL® or Verilog®, is placement. Placement refers to the process of assigning coordinate locations from an abstract grid representation of a particular target device, such as a programmable logic device (PLD), to various blocks and pins of the circuit design. The objective of placement is to assign locations such that signals linking the blocks and pins can be routed using minimal resources and/or meet established timing requirements.
Before the circuit design can be placed, the circuit design is mapped. A PLD such as Field Programmable Gate Array (FPGA), for example, can include an assortment of different component types such as memories, central processing units, and the like. Increasingly, logic blocks, or blocks, have been introduced into these devices to enhance application specific performance. When implementing a circuit design for a particular PLD, or target device, behavioral HDL must be mapped onto logic blocks of the target device. In illustration, Xilinx, Inc. of San Jose, Calif. manufactures various PLDs such as the Xilinx® Virtex4 family of FPGAs. These devices provide a plurality of different configurable logic blocks as described above. To implement the HDL circuit design, the HDL must be mapped onto the available blocks of the target device. Thus, if using a Xilinx® Virtex4 FPGA, the HDL must be mapped onto blocks available within, or upon, the selected Virtex4 FPGA.
The mapped circuit design then can be placed. Placement techniques largely are classified as either global or detailed. Generally, global placement produces a placed circuit design that includes overlaps, while detailed placement does not. An overlap refers to the situation in which more than one component has been assigned to a same site of the target device. A placement for a circuit design that includes one or more overlaps is said to be an infeasible placement in that the circuit design, in its current condition, is impossible to physically implement on the target device. In order to implement the circuit design, the overlaps must be removed.
As noted, removal of overlaps is the domain of detailed placement. Detailed placement typically operates on an initially placed circuit design, i.e. the output of a global placement algorithm or technique. Detailed placement refines the global placement to eliminate overlaps and/or otherwise improve the placement of the circuit design in accordance with established objectives. The result is a legal placement for the circuit design, i.e. one without overlaps.
Some varieties of detailed placement algorithms utilize a Breadth-First Search (BFS) technique. A BFS is a tree search algorithm commonly used for traversing a tree structure or graph. The BFS begins at the root node and explores all neighboring nodes. For each of the nearest nodes, the BFS explores the unexplored neighbor node, and so on, until the goal of the search is reached. A BFS is considered an uninformed search method in that it expands and examines all nodes of a graph systematically in search of a solution. The BFS exhaustively searches without consideration of the end goal. No heuristics are used. With respect to detailed placement, the BFS technique will select a first available site for a given block. In consequence, any solution considered when using a BFS technique is limited by order dependence, in reference to the order in which blocks are assigned to sites.
It would be beneficial to provide a technique for detailed placement that overcomes the limitations described above.